#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

// 最长子序列

class Solution
{
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2)
    {
        vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
        for (int i = 1; i <= s1.size(); ++i)
        {
            for (int j = 1; j <= s2.size(); ++j)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                if (s1[i - 1] == s2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            }
        }
        string res;
        int l1 = s1.size(), l2 = s2.size();
        for (; dp[l1][l2] > 0;)
        {
            if (s1[l1 - 1] == s2[l2 - 1])
            {
                res += s1[l1 - 1];
                --l1, --l2;
            }
            else
            {
                if (dp[l1 - 1][l2] > dp[l1][l2 - 1])
                {
                    --l1;
                }
                else
                {
                    --l2;
                }
            }
        }
        reverse(res.begin(), res.end());
        return res == "" ? "-1" : res;
    }
};

// 最长子串

class Solution
{
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2)
    {
        // write code here
        // 记录每个字符的位置
        unordered_map<char, vector<int>> chIndex;
        int size1 = str1.size();
        int size2 = str2.size();
        int maxSize = 0, maxIndex = -1, curIndex, curCount;
        int i, j;
        for (i = 0; i < size1; i++)
        {
            chIndex[str1[i]].emplace_back(i);
        }
        for (i = 0; i < size2; i++)
        {
            // 如果str2中的字符不在str1中
            if (chIndex.count(str2[i]) == 0)
                continue;
            // 如果str2中的字符在str1中，就遍历该字符在str1中的位置
            for (int x : chIndex[str2[i]])
            {
                // 如果当前位置的字符直到末尾都不能超过最长则放弃遍历之后的所有
                if ((size1 - x) < maxSize || (size2 - i) < maxSize)
                {
                    break;
                }
                curIndex = i;
                curCount = 0;
                j = i;
                // 通过比较两者相同的长度
                while (str1[x++] == str2[j++])
                {
                    curCount++;
                }
                if (curCount > maxSize)
                {
                    maxSize = curCount;
                    maxIndex = curIndex;
                }
            }
        }
        return maxSize > 0 ? str2.substr(maxIndex, maxSize) : string();
    }
};